package com.cg.offer;

import org.junit.Test;

/**
 * 剑指Offer 56-II.数组中数字出现的次数 II
 *
 * @program: LeetCode->Offer_56_II
 * @description: 剑指Offer 56-II.数组中数字出现的次数 II
 * @author: cg
 * @create: 2022-03-30 23:29
 **/
public class Offer_56_II {

    @Test
    public void test56_II() {
        System.out.println(singleNumber(new int[]{9, 1, 7, 9, 7, 9, 7}));
    }

    /**
     * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
     * <p>
     * 示例 1：
     * 输入：nums = [3,4,3,3]
     * 输出：4
     * <p>
     * 示例 2：
     * 输入：nums = [9,1,7,9,7,9,7]
     * 输出：1
     *  
     * 限制：
     * 1 <= nums.length <= 10000
     * 1 <= nums[i] < 2^31
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for (int num : nums) {
            for (int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0, m = 3;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }

}
